package com.zzz.sort.shell;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author zizan
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] array = new int[]{5, 1, 7, 4, 2, 7, 3, 1, 9};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    // 希尔排序就是加快速度简单的改进了插入排序，交换不相邻的元素以达到局部有序的效果
    // 插入排序时交换相邻，希尔是初始相邻间隔大于1的一个数
    private static void sort(int[] array) {

        int h = 1;
        // 计算h 初始大小  后续每执行完一轮h以h/3的速度减小
        while (h < array.length) h = h * 3 + 1;

        // 当h >= 1时，就继续缩小h
        while (h >= 1) {
            //分成h次插入排序
            for (int i = 0; i <= h - 1; i++) {

                // 按间隔h的数组进行插入排序 这里还改进了异步，如果只有if条件并且没有else操作，那么条件可以直接放入for中
                for (int j = i + h; j < array.length; j += h) {
                    // 为什么可以把放array[k] < array[k - h] 上面去 当array[k] >= array[k - h] 那么直接就退出了
                    // 也符合插入排序 bread的条件
                    for (int k = j; k > i && array[k] < array[k - h]; k -= h) {
                        int temp = array[k];
                        array[k] = array[k - h];
                        array[k - h] = temp;
                    }
                }
            }
            h /= 3;
        }
    }
}
